#include <iostream>
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <climits>
#include <math.h>
#include <queue>
#include <map>
#include <string>

using namespace std;

//max heap
//parent larger than children
struct Node{
        Node* parent;
        Node* left;
        Node* right;
        int val;
        pthread_mutex_t lock;
        Node (Node* m_parent = NULL, Node* m_left = NULL, Node* m_right = NULL, int m_val = INT_MIN) 
        : parent(m_parent), left(m_left), right(m_right), val(m_val){}
};


class heap{
  public: 
        heap (Node* m_root = NULL) : root(m_root){}
        ~heap(){destroy();} 
        void insert(int val);
        Node* search(int val); //low efficiency compared BST
        bool remove(int val);
        void destroy();
        void print();
        Node* find_min();
        Node* find_max();
        
        unsigned int getNodecnt(){return cur_node_cnt;}
        void increNodecnt(){cur_node_cnt++;}
        void decreNodecnt(){cur_node_cnt--;}
        
  private:
        void upHeap(Node* n);
        void downHeap(Node* n);
        void swap(Node* n1, Node* n2);
        void destroy(Node* leaf);
        
        Node* root;
        map<unsigned int, Node*> quickLU;
        unsigned int cur_node_cnt;
};
